﻿/* Author: Achim Schnell */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using AppFx.Tokenization;

namespace AppFx.Parsing
{
    /// <summary>
    /// Parses tokens into RPN-tokens.
    /// </summary>
    public class RpnParser
    {
        #region Constructors

        public RpnParser() { }

        #endregion

        #region Methods

        /// <summary>
        /// Parses the specified tokens.
        /// </summary>
        /// <param name="inputTokens">The tokens.</param>
        /// <returns></returns>
        public IList<IParsedToken> Parse(IEnumerable<IParsedToken> inputTokens)
        {
            List<IParsedToken> tokens = inputTokens.ToList();
            Queue<IParsedToken> output = new Queue<IParsedToken>();
            Stack<IParsedToken> ops = new Stack<IParsedToken>();

            int index = 0;
            while (index < tokens.Count)
            {
                switch (tokens[index].ParsedType)
                {
                    case eParsedTokenType.Number:
                        output.Enqueue(tokens[index]);
                        break;
                    case eParsedTokenType.Operator:
                        OperatorToken o1 = tokens[index] as OperatorToken;
                        if (ops.Count > 0)
                        {
                            IParsedToken peeked = ops.Peek();
                            while (peeked != null && peeked.ParsedType == eParsedTokenType.Operator)
                            {
                                OperatorToken o2 = peeked as OperatorToken;
                                if (o1.Precedence <= o2.Precedence)
                                {
                                    output.Enqueue(ops.Pop());
                                    peeked = null;
                                }
                                else
                                    break;
                                if (ops.Count > 0) { peeked = ops.Peek(); }
                            }
                        }
                        ops.Push(o1);
                        break;
                    case eParsedTokenType.L_Paren:
                        ops.Push(tokens[index]);
                        break;
                    case eParsedTokenType.R_Paren:
                        while (ops.Peek().ParsedType != eParsedTokenType.L_Paren)
                        {
                            output.Enqueue(ops.Pop());
                        }
                        ops.Pop();
                        if (ops.Peek().ParsedType == eParsedTokenType.Operator)
                            output.Enqueue(ops.Pop());
                        break;
                }
                index = index + 1;
            }

            while (ops.Count > 0)
            {
                output.Enqueue(ops.Pop());
            }

            return output.ToList();
        }

        #endregion
    }
}
